//	ID : pallab81
// 	PROG : 10139
// 	LANG : C++
// 	2011-06-14-11.02.11 Tuesday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define  CI( x ) scanf( "%d", &x )

#define VI vector<int>
#define VVI vector<VI >
#define VS vector<string>
#define VC vector<char>
#define VVC vector<VC >
#define VB vector<bool>
#define VVB vector<VB >
#define PAIR pair<int,int>
#define VP vector<PAIR >
#define fo(i,st,ed) for(int i = st; i < ed ; ++i)
#define foE(i,st,ed) for(int i = st; i <= ed ; ++i)
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define mk make_pair
#define f first
#define s second
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define ll long long
#define IO ifstream cin(".in") ; ofstream cout(".out");

//prime factorize the number
vector< pair<int,int> > fact;
int n,fac;
inline void F(long long n){
    fact.clear();
    for( long long i = 2; i*i <=n; ++i ){
        if( (n%i)==0 ){
            int d=0;
            while( (n%i)==0 ){
                n/=i;
                ++d;
            }
            fact.pb( mk(i,d) );
        }
    }
    if( n>1 ){
        fact.pb( mk(n,1) );
    }
}
inline bool good(int prime, int powerNeed, int val){
    int total=0;
    for( long long i=prime; i<=val ; i*=prime ){
        total+= (val/i);
    }

    //cout<<prime<<" "<<powerNeed<<" "<<val<<" total "<<total;bip;
    return ( total>=powerNeed);
}
inline void doit(){
    bool allOk=true;
    fo(i,0,SZ(fact)){
        if( good( fact[i].f, fact[i].s, fac)==false ){
            allOk=false;
            goto L;
        }
    }
L:
    if(allOk==true){
        printf("%d divides %d!\n",n,fac);
    }
    else{
        printf("%d does not divide %d!\n",n,fac);
    }
return ;
}

int main(){
    while( scanf("%d %d",&fac,&n)!= EOF ){
        F(n);
        doit();
    }

return 0;
}

